package 越长越合法

// 这题得用逆向思维 bad窗口维护 越短越合法 与越长越合法的转换
// 注意等号 = !!
func numberOfSubstrings(s string, k int) int {
	//dic := make([]int, 26)
	//left := 0
	//ans := 0z
	//for _, c := range s {
	//	dic[c-'a']++
	//	for {
	//		for _, i := range dic {
	//			if i >= k {
	//				dic[left]--
	//				left++
	//				break
	//			}
	//		}
	//	}
	//	ans += left
	//}
	//return ans
	n := len(s)
	total := n * (n + 1) / 2
	freq := make([]int, 26)
	left := 0
	bad := 0
	for right, c := range s {
		freq[c-'a']++
		for freq[c-'a'] >= k {
			freq[s[left]-'a']--
			left++
		}
		bad += right - left + 1
	}
	return total - bad
}
